home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Chip 1996 April
/
CHIP 1996 aprilis (CD06).zip
/
CHIP_CD06.ISO
/
hypertxt.arj
/
9508
/
E_MESSZE.CD
< prev
next >
Wrap
Text File
|
1996-03-10
|
8KB
|
149 lines
@VRejtvénymegfejtés@N
@VAutózzunk...@N
..minél messzebbre címmel jelent meg áprilisi számunkban
fejtörônk. Az alábbiakban a megoldásokat közöljük.
A feladat: a lehetô legtávolabbra kellene eljutnunk
üzemanyagbázisunkról 50 literes benzintankú autónkkal, amely
100 km-enként 10 liter benzint fogyaszt, és induláskor
tankja tele van. A bázison @KN@N darab 200 literes hordó áll
rendelkezésünkre, tele benzinnel, azonban egyszerre csak egy
hordót tudunk magunkkal vinni, függetlenül annak
telítettségi fokától.
A rejtvényre hat megfejtés érkezett, különféle formákban
és úton. A hagyományos levél, illetve lemez mellett nagy
örömünkre már kaptunk megfejtéseket e-mailen is. A Pascal--C
verseny jelenleg döntetlenre áll, s ráadásként (Bonifert
Csaba jóvoltából) feltûnt egy új nyelv is, a Linux alatti
Common Lisp.
Megfejtôink többsége (5:1 arányban) lényegében a
következô gondolatmenet szerint okoskodott (Barczikay Zsolt,
illetve Pittner Ferenc dokumentációja alapján). Barczikay
Zsolt: ""Természetesen fel kell használnunk az összes
benzint, hogy legtávolabb juthassunk, ehhez viszont az
összes hordót ki kell ürítenünk. Az összes hordó
elôreviteléhez folyton oda-vissza kell szaladgálnunk.
Legcélszerûbb kiválasztani egy akkora távolságot, amekkorán
egy tanknyi benzinnel átvihetjük minden hordónkat. @KN@N hordó
esetén @K2*N-1@N-szer kell megtennünk ezt a távot, amely így
@K500/(2*N-1)@N-nek adódik. Ekkor tankolunk, majd ismételjük az
eljárást. Természetesen tankolás után ellenôrizzük, hogy nem
ürült-e ki valamelyik hordó, hiszen azt ekkor már nem kell
cipelnünk. Amikor már csak egy hordónk marad (és tele
tankunk) akkor még 2500 km-t tudunk menni." Olvasónk ezen
algoritmus alapján mintegy szimulálta az utat. Pittner
Ferenc matematikai összefüggést állított fel a hordók száma
és a megtett út között.
Olvasónk (s még Varga József, Tóth László)
végeredményben ezen képlet kiszámítására írt programot.
Eredményeik 1, 2, 3, 10 hordóra 2500, 3166,67, 3566,67,
4766,51 km.
Egészen más gondolatmenetet követett Bonifert Csaba. ï
nem tartotta szükségesnek a hordók ""egyszerre" történô
mozgatását, illetve a minden @KN@N-re az azonos ""menetrendet".
îgy a fenti hordószámokra a következô távolságokat kapta:
2500, 3083,3 (ami biztosan nem optimális), 3633,3, 5046,6
(amik lehetnek optimálisak). ""A megoldás durva algoritmusa
-- írja levelében --:
1. Jelöljünk ki egy új állomást az aktuális állomástól B
távolságra (B<=500).
2. Amennyi hordót csak tudunk, vigyünk át az új
állomásra.
3. Ha már csak egy hordónk van, menjünk addig, amíg a
benzinünk el nem fogy.
4. Egyébként folytassuk az 1. lépéssel.
Az algoritmusban gyakorlatilag két lépést ismételgetünk:
az aktuális állomásról egy hordót átviszünk a következô
állomásra, illetve visszamegyünk egy állomást, hordó nélkül.
A fô probléma, hogy milyen távolságra legyen az új állomás.
Åltalában igaz, hogy az állomasok közötti távolság nem lehet
nagyobb 500 km-nél, mert akkor nem tudnánk visszamenni.
Addig mindegy az új állomás távolsága, amíg közben nem ürül
ki hordó, vagy nem csappan meg annyira a tartalma, hogy már
nem érdemes visszamenni érte.
Tegyük fel, hogy az @KA(x)@N állomáson @KK@N db tele hordó és az
autó tankjában @KT@N benzin van. ùgy kell megválasztani az
@KA(x+1)@N állomás távolságát, hogy:
-- mindig tele hordókat vigyünk át A(x+1)-re;
-- visszainduláskor ne kelljen az átvitt hordóból
tankolnunk;
-- az utolsó hordó átvitelénél induláskor az autó tankja
tele legyen;
-- a szállítás teljes benzinigényét pontosan fedezze az
egy darab A(x)-on maradt hordó.
E négy feltételbôl következik, hogy @KK-1@N darab hordót
viszünk át, összesen @K2*(K-2)@N-szer tesszük meg a két állomás
közötti távot, tehát fennáll az alábbi összefüggés:
@KK*200+T=(K-1)*200+2*(K-2)*B+50@N
(Az utolsó induláskor tele a tank, ez a + 50 liter, @KB@N a
két állomás távolsága literben.) Az egyenletbôl:
@KB=(150+T)/(2*K-4)@N
Tehát így kell(ene) megválasztani a következô állomás
távolságát, de ez az összefüggés csak 5 tele hordó fölött
használható, mert @KB@N maximum 25 liter lehet, hogy ne kelljen
visszafele tankolni az átvitt hordóból. Ezért öt vagy
kevesebb hordó esetén más megoldást kell keresni, melynek
lényege, hogy a két fenti lépés közé be kell iktatni egy
(vagy több) olyan szállítást, amikor nem csökken a hordók
száma." A megoldás részletei kiolvashatók megfejtônk C
nyelvû programjából, mely a CT BBS-en megtalálható. A
BBS-hez hozzá nem férôk számára álljon itt az @KN=3@N eset egy
lehetséges ""aprópénzre váltása":
1. 1. hordót 250 km-re elvisszük (S1 segéd-állomás).
2. Tankot feltöltjük H1-bôl (H1=175).
3. Vissza a bázisra.
4. 2. hordót S1-re visszük.
5. Tankot feltöltjük H1-bôl (H1=125).
6. Vissza a bázisra.
7. 3. hordó S1-re.
8. Tankot feltöltjük H1-bôl (H1=75).
9. 2. hordót elôre 50 km-rel (A1 állomás, távolsága a
bázistól 300 km).
10. Vissza S1-re.
11. 3. hordót A1-re.
12. Vissza S1-re.
13. 1. hordót A1-re.
14. Tankot feltöltjük H1-bôl (H1=50, T=50).
15. 2. hordót elôre 250 km-rel (A2 állomás, távolsága
A1-tôl 250 km).
16. Vissza A1-re.
17. Tankot feltöltjük H1-bôl (H1=0!).
18. 3. hordót elôre 500 km-t (S2 állomás).
19. Tankot feltöltjük H3-bôl (H3=150).
20. Vissza A2-re.
21. 2. hordót S2-re.
22. Tankot feltöltjük H3-bôl (H3=100).
23. 2. hordót 250 km-rel elôre (S3 állomás).
24. Vissza S2-re.
25. Tankot feltöltjük H3-bôl (H1=50).
26. 3. hordót S3-re.
27. 2. hordót elôre 83.333 km-t (A3 állomás, távolsága
A2-tôl 583,3 km).
28. Vissza S3-ra.
29. 3. hordót A3-ra.
30. Tankot feltöltjük H3-bôl (H3=0, T=50, H2=200).
31. Innen 2500 km tehetô meg.
Tehát az összes út 300+250+583,3+2500=3633,3 km.
A hónap nyertese Bonifert Csaba, most kivételesen nem a
szerencse, hanem a távolság okán.
@VBánhegyesi Zoltán@N
@Vùj rejtvényünk@N
@VIsmét hordók@N
A feladat ""körítése" hasonló áprilisi rejtvényünkéhez,
de a feltételek mások. Egy körút mentén hordók vannak
elhelyezve tetszôlegesen, különbözô mennyiségû (de nullánál
több) benzinnel, de a hordókban található benzin
összmennyisége pontosan a teljes körutazás megtételéhez
szükséges adaggal egyezik meg. A gépkocsi tankja rugalmas:
mindig képes befogadni az aktuális hordó tartalmát. A
feladat annak meghatározása, hogy a (kezdetben üres
tartályú) autó hol kezdje útját, s milyen irányban haladjon.
Beküldési határidô: 1995. augusztus 30.